import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class ChangingSounds
{
	public int[] list;
	public int mmax;
	public Integer[][] mark;
	public int maxFinal(int[] changeIntervals, int beginLevel, int maxLevel)
	{
		mmax = maxLevel;
		list = changeIntervals;
		mark = new Integer[list.length+2][mmax+1];
		return solve(0, beginLevel);
	}

	public int solve(int index, int level){
		if(level > mmax) return -1;
		if(level < 0) return -1;
		if(index == list.length) return level;
		if(mark[index][level] != null) return mark[index][level];
		int ret = -1;
		ret = Math.max(ret, solve(index+1, level + list[index]));
		ret = Math.max(ret, solve(index+1, level - list[index]));
		return mark[index][level] = ret;
	}
	
	public static void main(String[] args)
	{
		long time;
		int answer;
		boolean errors = false;
		int desiredAnswer;
		
		
		time = System.currentTimeMillis();
		answer = new ChangingSounds().maxFinal(new int[]{5, 3, 7}, 5, 10);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 10;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new ChangingSounds().maxFinal(new int[]{15, 2, 9, 10}, 8, 20);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = -1;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		time = System.currentTimeMillis();
		answer = new ChangingSounds().maxFinal(new int[]{74,39,127,95,63,140,99,96,154,18,137,162,14,88}, 40, 243);
		System.out.println("Time: " + (System.currentTimeMillis()-time)/1000.0 + " seconds");
		desiredAnswer = 238;
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		System.out.println("Desired answer:");
		System.out.println("\t" + desiredAnswer);
		if (answer != desiredAnswer)
		{
			errors = true;
			System.out.println("DOESN'T MATCH!!!!");
		}
		else
			System.out.println("Match :-)");
		System.out.println();
		
		
		if (errors)
			System.out.println("Some of the test cases had errors :-(");
		else
			System.out.println("You're a stud (at least on the test data)! :-D ");
	}

}
//Powered by [KawigiEdit] 2.0!
